// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-02 11:56
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeSet;

@SuppressWarnings("ALL")
/**
 * 最繁忙服务器:三叶解法
 */
public class BusiestService {
    public List<Integer> busiestServersT(int k, int[] arrival, int[] load) {
        int n = arrival.length, max = 0;
        PriorityQueue<int[]> busyService = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        TreeSet<Integer> freeService = new TreeSet<Integer>();
        int[] cnt = new int[k];
        for (int i = 0; i < k; i++) {
            freeService.add(i);
        }
        for (int i = 0; i < n; i++) {
            int start = arrival[i], end = start + load[i];
            while (!busyService.isEmpty() && busyService.peek()[1] <= start) {
                freeService.add(busyService.poll()[0]);
            }
            Integer u = freeService.ceiling(i % k);
            if (u == null) {
                u = freeService.ceiling(0);
            }
            if (u == null) {
                continue;
            }
            freeService.remove(u);
            busyService.add(new int[]{u, end});
            max = Math.max(max, ++cnt[u]);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (cnt[i] == max) {
                ans.add(i);
            }
        }
        return ans;
    }


}
